#ifndef _K_BEST_H__K_BEST_H_
#define _K_BEST_H_

#include <deque>
#include <algorithm>

template<typename R, typename V>
class kbest {
public:
	typedef R result_type;
	typedef V result_value_type;

	kbest(unsigned int k = 3, unsigned int m = 100, double e = 0.05) :
		k_threshold(k), restrain_limit(m), max_error(e), count(0)
	{
	}

private:
	unsigned int k_threshold;
	unsigned int restrain_limit;
	double max_error;

	result_type best_res;
	std::deque<result_value_type> k_best_value;
	size_t count;

public:
	int add(const result_type & result, result_value_type value)
	{
		if (++count > restrain_limit) {
			return -1;
		}

		if (0 == k_best_value.size()) {
			k_best_value.push_back(value);
			best_res = result;
			return 0;
		}

		double error = (double) (value - k_best_value[0]) / k_best_value[0];

		if (error < 0) {
			best_res = result;
			k_best_value.push_front(value);

			typename std::deque<result_value_type>::iterator it;
			it = k_best_value.begin();
			for (++it; it != k_best_value.end(); ++it) {
				if ((double) (*it - value) / value > max_error) {
					break;
				}
			}
			k_best_value.erase(it, k_best_value.end());

			if (k_best_value.size() >= k_threshold) {
				return 1;
			}
			else {
				return 0;
			}
		}
		else if (error < restrain_limit) {
			k_best_value.push_back(value);
			if (k_best_value.size() >= k_threshold) {
				return 1;
			}
			std::sort(k_best_value.begin(), k_best_value.end());
		}

		return 0;

	}

	result_type get_result()
	{
		//std::cout << count << std::endl;
		return best_res;
	}

};

#endif /*_K_BEST_H_*/
